package com.sicheng.lc.杂题.路径问题;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/18 10:42
 */
public class Lazy推箱子 {

    //https://leetcode.cn/problems/minimum-moves-to-move-a-box-to-their-target-location/
    static int[][] d = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

    // 状态 {i, j, x, y, step}
    // {人的坐标，箱子的坐标，箱子移动步数}
    // 拓展新节点是状态必须不同，否则是无用功
    boolean[][][][] visit = new boolean[20][20][20][20];

    public int minPushBox(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int px = 0, py = 0, bx = 0, by = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 'B') {
                    bx = i;
                    by = j;
                } else if (grid[i][j] == 'S') {
                    px = i;
                    py = j;
                }
            }
        }
        int[] s = {px, py, bx, by, 0};
        visit[px][py][bx][by] = true;
        PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[4]));
        heap.offer(s);

        while (!heap.isEmpty()) {

            int size = heap.size();
            for (int l = 0; l < size; l++) {
                int[] p = heap.poll();
                assert p != null;
                for (int[] dd : d) {
                    int npx = p[0] + dd[0];
                    int npy = p[1] + dd[1];
                    int nbx = p[2];
                    int nby = p[3];
                    int step = p[4];

                    if (npx == nbx && npy == nby) {
                        nbx += dd[0];
                        nby += dd[1];
                        step++;
                    }

                    if (npx < 0 || npx >= m || nbx < 0 || nbx >= m ||
                            npy < 0 || npy >= n || nby < 0 || nby >= n ||
                            grid[npx][npy] == '#' || grid[nbx][nby] == '#'
                    )
                        continue;

                    if (!visit[npx][npy][nbx][nby]) {
                        if (grid[nbx][nby] == 'T')
                            return step;

                        heap.offer(new int[]{npx, npy, nbx, nby, step});
                        visit[npx][npy][nbx][nby] = true;
                    }
                }
            }
        }

        return -1;
    }
}
